local t = {}

for i = 1, 4 do
    table.insert(t, math.random(i), i);
end

local function dump()
    print(table.concat(t, ","));
end


function bubble_sort()
    print("this is fun: bubble_sort")
    dump()
    local n = #t
    for j= 1, n-1 do
        print(j)
        for i = 1, n-j do
            -- print(i,"|",t[i],t[j])
            if t[i] > t[i+1] then
                t[i], t[i+1] = t[i+1],t[i]
            end
        end
    end
    dump()
end

function quick_sort()
    print("快速排序")
    local function sort(left, right)
        if left >= right then
            return ;
        end;
        local i     = left;
        local j     = right;
        local key   = t[left];
        while (i < j) do
            while i < j and key <= t[j] do
                j = j - 1;
            end;
            t[i] =  t[j];
            dump()
            while i < j and key >= t[i] do
                i = i + 1;
            end;
            t[j] = t[i];
            dump()
        end;
        t[i] = key;
        dump()
        sort(left, i - 1);
        sort(i + 1, right);
    end;
    sort(1, #t)
end;

--[[--
-   partition: 获得快排中介值位置
-   @param: list, low, high - 参数描述
-   @return: pivotKeyIndex - 中介值索引
]]
function partition(list, low, high)
    local low = low
    local high = high
    local pivotKey = list[low] -- 定义一个中介值
    
    -- 下面将中介值移动到列表的中间
    -- 当左索引与右索引相邻时停止循环
    while low < high do
        -- 假如当前右值大于等于中介值则右索引左移
        -- 否则交换中介值和右值位置
        while low < high and list[high] >= pivotKey do
            high = high - 1
        end
        swap(list, low, high)

        -- 假如当前左值小于等于中介值则左索引右移
        -- 否则交换中介值和左值位置
        while low < high and list[low] <= pivotKey do
            low = low + 1
        end
        swap(list, low, high)
    end
    return low
end

--[[--
-   orderByQuick: 快速排序
-   @param: list, low, high - 参数描述
-    @return: list - table
]]
function orderByQuick(list, low, high)
    if low < high then
        -- 返回列表中中介值所在的位置，该位置左边的值都小于等于中介值，右边的值都大于等于中介值
        local pivotKeyIndex = partition(list, low, high)
        -- 分别将中介值左右两边的列表递归快排
        orderByQuick(list, low, pivotKeyIndex - 1)
        orderByQuick(list, pivotKeyIndex + 1, high)
    end
end